/*
 * 1366.斐波纳契数列
 * 查找斐波纳契数列中第 N 个数。
 * 所谓的斐波纳契数列是指：前2个数是 0 和 1 。第 i 个数是第 i-1 个数和第i-2 个数的和。
 * https://www.lintcode.com/problem/fibonacci/description
 * 
 * 斐波纳契数列的前10个数字是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
 * 
 * 样例
 * 给定 1，返回 0
 * 给定 2，返回 1
 * 给定 10，返回 34
 */
package fibonacci_1366;

public class Fibonacci_1366 {
	
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public static int fibonacci(int n) {
        // write your code here
    	int firstNum = 0;
    	int secondNum = 1;
    	if(n == 1) {
    		return firstNum;
    	}  else {
    		for(int i = 2; i < n; ++i) {
    			int tmp = firstNum + secondNum;
    			firstNum = secondNum;
    			secondNum = tmp;
    		}
    	}
    	
    	return secondNum;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(fibonacci(10));

	}

}
